package base_Suanfa.dongtaiguihua;

public class min_coins {
    //暴力递归算法  至顶向下，重复搜索，有重叠子问题  可选纸币有25 20 5 1
    public static  int coins(int n){
        if(n<1) return Integer.MAX_VALUE;
        if(n==25||n==20||n==5||n==1) return 1;
        int m=Math.min(coins(n-25),coins(n-20));
        int m1=Math.min(coins(n-5),coins(n-1));
        return Math.min(m,m1)+1;
    }
    //记忆化搜索 自顶向下
    public static  int coins1(int n,int dp[] ){
        if(n<1) return Integer.MAX_VALUE;
        if(dp[n]==0) {
            int m = Math.min(coins1(n - 25,dp), coins1(n - 20,dp));
            int m1 = Math.min(coins1(n - 5,dp), coins1(n - 1,dp));
            dp[n]=Math.min(m,m1)+1;
        }
        return  dp[n];

    }
    //采用递推方式，自底向上  不需要初始化dp数组
    public static  int coins2(int n,int dp[],int face[] ){
        if(n<1) return 0;
        for(int i=1;i<=n;i++) {
            int min = dp[i - 1];     //直接初始化为i-1
            face[i]=1;
            if (i >= 5&&dp[i-5]<min){
                min=dp[i-5];
                face[i]=5;
            };
            if (i >= 20&&dp[i-20]<min){
                min=dp[i-20];
                face[i]=20;
            };
            if (i >= 25&&dp[i-25]<min){
                min=dp[i-25];
                face[i]=25;
            };
            dp[i]=min+1;
        }
        return dp[n];
    }
    public static void main(String[] args) {
        int dp[]=new int[42];   //用来保存上一次计算的结果
//        dp[1]=1;
//        dp[5]=1;
//        dp[20]=1;
//        dp[25]=1;
//        System.out.println(coins(41));
//        System.out.println(coins1(41,dp));
        int face[]=new int[dp.length];//用来保存当前选定的面值
        System.out.println(coins2(41,dp,face));
        System.out.println("选取的硬币面值分别是");
        int n=41;
        while(n>0){
            System.out.print(face[n]+"   ");
            n=n-face[n];      //直接减去面值
        }
    }
}
